import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class AdaptiveArithmeticCoding {
	public static String code(byte[] x, boolean isDCoding) throws UnsupportedEncodingException {
        final Fraction ONE = new Fraction(1, 1);
        final Fraction ZERO = new Fraction(0, 1);
		Fraction F = ZERO;
		Fraction G = ONE;

        Map<Byte, Integer> index = new HashMap<Byte, Integer>();
        List<Fraction> p = new ArrayList<Fraction>(257);
        List<Fraction> q = new ArrayList<Fraction>(257);
        List<Byte> symbols = new ArrayList<Byte>(256);

        p.add(ONE);
        q.add(ONE);

        int[] tau = new int[256];

        System.out.println("\\begin{tabular}{|l|l|l|l|l|l|}\\hline");
		System.out.println("$i$ & $x_i$ & $p(x_i)$ & $q(x_i)$ & $F$ & $G$ \\\\\\hline");
        
		for (int i = 0; i < x.length; i++) {
            byte curr = x[i];
            
            System.out.print(i + " & " + new String(new byte[] {x[i]}, "cp1251").charAt(0) + " & ");
            
            if (!index.containsKey(curr)) {
                //Writing escape
                F = F.add(G.multiply(q.get(0)));
                G = G.multiply(p.get(0));
                //System.err.println(p.get(0));

                int myPosition = 0;
                for (byte s = 0; s < curr; ++s) {
                    if (!index.containsKey(s)) {
                        ++myPosition;
                    }
                }
                int mn = symbols.size();
                Fraction myP, myQ;
                myP = new Fraction(1, 256 - mn);
                myQ = new Fraction(myPosition, 256 - mn);
                
                System.out.print(myP + " & " + myQ + " & ");

                //Writing the new symbol
                F = F.add(G.multiply(myQ));
                G = G.multiply(myP);
                //System.err.println(myP);

                p.add(null);
                q.add(null);
                index.put(curr, index.size() + 1);
                symbols.add(curr);
            } else {
                int code = index.get(curr);
                F = F.add(G.multiply(q.get(code)));
                G = G.multiply(p.get(code));
                //System.err.println(p.get(code));
                
                System.out.print(p.get(code) + " & " + q.get(code) + " & ");
            }
            
            System.out.println(F + " & " + G + "\\\\\\hline");

            tau[curr & 255]++;

            int mn = symbols.size();
            int n = i + 1;

            if (isDCoding) {
                p.set(0, new Fraction(mn, 2 * n));
            } else {
                p.set(0, new Fraction(1, n + 1));
            }
            q.set(0, ZERO);

            for (int t = 0; t < mn; ++t) {
                byte b = symbols.get(t);
                if (isDCoding) {
                    p.set(t + 1, new Fraction(2 * tau[b & 255] - 1, 2 * n));
                } else {
                    p.set(t + 1, new Fraction(tau[b & 255], n + 1));
                }
                q.set(t + 1, q.get(t).add(p.get(t)));
            }
		}
		
		System.out.println("\\end{tabular}");

        Fraction value = F.add(G.multiply(new Fraction(1, 2)));
		int z = G.inverse().log2up() + 1;
        StringBuilder result = new StringBuilder();
		String out = value.nBitsAfterComma(z).toString(2);
		while (result.length() + out.length() < z) {
            result.append("0");
		}
        result.append(out);
        return result.toString();
	}
	
	public static void main (String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"), "cp1251"));
        String input = in.readLine();
        in.close();
		String output = code(input.getBytes("cp1251"), false);
		System.out.println();
		System.out.println(output);
		System.out.println("Input length: " + input.length() * 8 + " bits");
		System.out.println("Output length: " + output.length() + " bits");
	}
}	
